package com.muchfish.algorithm.array;
/**
 * <a href="https://leetcode.cn/problems/rotate-array/description/">题目：189. 轮转数组</a>
 * <br>
 * 题目描述：<br>
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。<br>
 * 解题思路：<br>
 * 1. 额外数组：<br>
 * 1.1 将数组中的每个元素放到它应该被放置的位置，即 (i + k) % nums.length 位置上。<br>
 *  （取余：i+k是nums.length的n倍多m,m即为最终的索引位。m的范围是0~nums.length-1，所以是对nums.length 取余）
 * 1.2 复制 temp 数组到 nums 数组中。<br>
 * 2. 环状替换：<br>
 * <img src="https://pic.leetcode-cn.com/f0493a97cdb7bc46b37306ca14e555451496f9f9c21effcad8517a81a26f30d6-image.png">
 * 2.1
 * an=bk？<br>
 * a为圈数，n为数组元素个数，将轮转当作往前跑，an为经历的的长度。b为经历的元素个数（轮转次数），k为每次向右轮转 k 个位置，将轮转当作往前跑，bk为经历的的长度。所以有an=bk<br>
 * 3.反转法，数字规律
 * 3.1 反转整个数组（首位双指针法进行翻转）<br>
 * 3.2 反转前 k 个元素<br>
 * 3.3 反转后 n-k 个元素<br>
 */
public class Array11 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        rotate(nums, 3);
    }

    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        // 反转整个数组
        reverse(nums, 0, nums.length - 1);
        // 反转前 k 个元素
        reverse(nums, 0, k - 1);
        // 反转后 n-k 个元素
        reverse(nums, k, nums.length - 1);
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }


    public static void rotate3(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    private static int gcd(int x, int y) {
        return y  > 0 ? gcd(y, x % y) : x;
    }

    public static void rotate2(int[] nums, int k) {
        //额外数组
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(temp, 0, nums, 0, nums.length);
    }
    public static void rotate1(int[] nums, int k) {
        //额外数组
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            //错误做法 nums =[-1] k=2时，执行报错java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
            temp[(i + k) >  nums.length-1?i+k-nums.length:i+k] = nums[i];
        }
        System.arraycopy(temp, 0, nums, 0, nums.length);
    }
}
